package P222_完全二叉树节点个数;
// 完全二叉树的节点个数
  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }

        int leftCount = countNodes(root.left);
        int rightCount = countNodes(root.right);
        return 1 + leftCount + rightCount;
    }

    //用完全二叉树的规律来做
    //完全二叉树，是只有最后一层可能出现空节点，并且是靠左的（如果最后一层有节点，那么都是从左到右的，只有右边可能有空节点）

    //从root开始，判断他的左侧子树高度为LeftHigh,右侧子树的高度为RightHigh
    //根据完全二叉树的规律
    //如果LeftHigh = RightHigh ,这表示起码整个左子树是满二叉树（那么他的节点数就是2^LeftHigh - 1)
    //如果LeftHigh > RightHigh,这表示最下面一层右边的没有，左边有。这个时候呢，我们可以判断他们的上一层是满的，上一层的高度是RightHigh

    public int getHigh(TreeNode root){
        TreeNode x = root;
        int count = 0;
        while(x != null){
            count ++;
            x = x.left;
        }
        return count;
    }
    public int countNodes2(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHigh = getHigh(root.left);
        int rightHigh = getHigh(root.right);
        if(leftHigh > rightHigh){
            //左边 高于 右边
            //上一层的子满二叉树高度是rightHigh, 右边子树节点是2^rightHigh - 1，
            //我们把这个以及root节点一起排除掉，就是2^rightHigh个节点。左边还剩下root.left，这个继续循环计算
            //注意!!!  + 比 <<的优先级要高，所以下面的 1<<rightHigh需要加上括号
            return countNodes2(root.left) + (1<<rightHigh);
        }
        //两边高度相同，那么左边是满子树
        return countNodes2(root.right) + (1<<leftHigh);

    }

    public static  void main(String args[]){
        TreeNode Node1 = new TreeNode(1);
        TreeNode Node2 = new TreeNode(2);
        TreeNode Node3 = new TreeNode(3);
        TreeNode Node4 = new TreeNode(4);
        TreeNode Node5 = new TreeNode(5);
        TreeNode Node6 = new TreeNode(6);
        Node1.left = Node2;
        Node1.right = Node3;
        Node2.left = Node4;
        Node2.right = Node5;
        Node3.left = Node6;
        System.out.println(new Solution().countNodes2(Node1));
        System.out.println(2+1<<3);
        System.out.println(2+(1<<3));

    }
}

